#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 1838. 最高频元素的频数
// https://leetcode.cn/problems/frequency-of-the-most-frequent-element/description/

class Solution1 {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int ans = 1;
        sort(nums.begin(), nums.end(), greater<int>());
        int left = 0;
        for (int i = 1; i < nums.size(); i++)
        {
            int curNum = nums[i];
            while(nums[left] - curNum > k){
                k += (i - left - 1) * (nums[left] - nums[left + 1]);
                left++;
                continue;
            }
            k -= (nums[left] - curNum);
            ans = max(i - left + 1, ans);
        }
        return ans;
    }
};

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int left = 0;
        int ans = 0;
        long long sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            long long curNum = nums[i];
            sum += curNum;
            while((i - left + 1) * curNum - sum > k){
                sum -= nums[left];
                left++;
            }
            ans = max(ans, i - left + 1);
        }
        return ans;
    }
};


int main()
{
    return 0;
}